#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

void PrintNums(int* nums, int numsSize)
{
	for (int i = 0; i < numsSize; i++)
		printf("%d ", nums[i]);

	printf("\n");
}

void Swap(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void InsertSort(int* nums, int numsSize)
{
	for (int i = 0; i < numsSize - 1; i++)
	{
		int end = i;
		int temp = nums[end + 1];

		while (end >= 0)
		{
			if (temp < nums[end])
			{
				nums[end + 1] = nums[end];
				end--;
			}
			else
				break;
		}

		nums[end + 1] = temp;
	}
}


void ShellSort(int* nums, int numsSize)
{
	int gap = numsSize;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < numsSize - gap; i++)
		{
			int end = i;
			int temp = nums[end + gap];

			while (end >= 0)
			{
				if (temp < nums[end])
				{
					nums[end + gap] = nums[end];
					end -= gap;
				}
				else
					break;
			}

			nums[end + gap] = temp;
		}
	}
}

void SelectSort(int* nums, int numsSize)
{
	int begin = 0;
	int end = numsSize - 1;

	while (begin < end)
	{
		int max_index = begin;
		int min_index = begin;

		for (int i = begin; i <= end; i++)
		{
			if (nums[i] > nums[max_index])
				max_index = i;
			if (nums[i] < nums[min_index])
				min_index = i;
		}

		Swap(&nums[begin], &nums[min_index]);
		if (max_index == begin)
			max_index = min_index;
		Swap(&nums[end], &nums[max_index]);

		end--;
		begin++;
	}
}

void AdjustDown(int* nums, int numsSize, int parent)
{
	int child = parent * 2 + 1;

	while (child < numsSize)
	{
		if (nums[child + 1] > nums[child])
			child = child + 1;

		if (nums[parent] < nums[child])
		{
			Swap(&nums[parent], &nums[child]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapSort(int* nums, int numsSize)
{
	for (int i = (numsSize - 2) / 2; i >= 0; i--)
		AdjustDown(nums, numsSize, i);

	int end = numsSize - 1;
	while (end > 0)
	{
		Swap(&nums[0], &nums[end]);
		end--;

		AdjustDown(nums, end, 0);
	}
}

void BubbleSort(int* nums, int numsSize)
{
	for (int i = 0; i < numsSize - 1; i++)
	{
		int flag = 0;

		for (int j = 0; j < numsSize - i - 1; j++)
		{
			if (nums[j] > nums[j + 1])
			{
				Swap(&nums[j], &nums[j + 1]);
				flag = 1;
			}
		}

		if (flag == 0)
			break;
	}
}

int main()
{
	int* nums[] = { 9, 3, 1, 2, 7, 4, 8, 5, 6 };
	int numsSize = sizeof(nums) / sizeof(int);

	//InsertSort(nums, numsSize);
	//ShellSort(nums, numsSize);
	//SelectSort(nums, numsSize);
	//HeapSort(nums, numsSize);
	BubbleSort(nums, numsSize);

	PrintNums(nums, numsSize);

	return 0;
}